
class Solution {
    vector<int> v;
    void mergeSort (vector<int>& nums, int l, int r) {
        if(l >= r) return ;
        int mid = (r-l)/2 + l;
        mergeSort(nums, l, mid);  //对 nums 数组里 [l,mid]部分进行排序
        mergeSort(nums, mid+1, r); //对 nums 数组里 [mid+1,r]部分进行排序
        // 合并两个有序区间
        int i = l, j = mid+1;   // 双指针分别是两个区间的下标
        int index = 0;
        while(i <= mid && j <= r){
            if(nums[i] <= nums[j]) v[index++] = nums[i++];
            else v[index++] = nums[j++];
        }
        while(i <= mid) v[index++] = nums[i++];
        while(j <= r) v[index++] = nums[j++];
        // 将排序后区间元素放入原区间
        for (int i = 0; i < r-l+1; ++i) {
            nums[i + l] = v[i];
        }
    }
public:
    vector<int> sortArray(vector<int>& nums) {
        v = nums;
        mergeSort(nums, 0, nums.size()-1);
        return nums;
    }
};